EMDUnifrac: Exact Linear Time Computation of the Unifrac Metric and Identification of Differentially Abundant Organisms

摘要

Both the weighted and unweighted Unifrac distances have been verysuccessfully employed to assess if two communities differ, but do not give anyinformation about how two communities differ. We take advantage of recentobservations that the Unifrac metric is equivalent to the so-called earthmover's distance (also known as the Kantorovich-Rubinstein metric) to developan algorithm that not only computes the Unifrac distance in linear time andspace, but also simultaneously finds which operational taxonomic units areresponsible for the observed differences between samples. This allows thealgorithm, called EMDUnifrac, to determine why given samples are different, notjust if they are different, and with no added computational burden. EMDUnifraccan be utilized on any distribution on a tree, and so is particularly suitableto analyzing both operational taxonomic units derived from amplicon sequencing,as well as community profiles resulting from classifying whole genome shotgunmetagenomes. The EMDUnifrac source code (written in python) is freely availableat: https://github.com/dkoslicki/EMDUnifrac.